package codingforgreat.class35;

import java.util.*;

public class Lc673 {

    public int findNumberOfLIS1(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        ArrayList<TreeMap<Integer,Integer>> dp = new ArrayList<>();
        int len = 0;
        int cnt = 0;
        for(int num : nums){
            //找到<=num的长度
            len = search(dp,num);
            if(len == 0){
                cnt = 1;
            }else{
                TreeMap<Integer,Integer> p = dp.get(len - 1);
                cnt = p.firstEntry().getValue() - (p.ceilingKey(num) != null ? p.get(p.ceilingKey(num)) : 0);
            }
            if(len == dp.size()){
                dp.add(new TreeMap<Integer,Integer>());
                dp.get(len).put(num,cnt);
            }else{
                dp.get(len).put(num,dp.get(len).firstEntry().getValue() + cnt);
            }
        }
        return dp.get(dp.size() - 1).firstEntry().getValue();

    }
    //>=num最左位置
    public int search(ArrayList<TreeMap<Integer,Integer>> dp,int num){
        int L = 0;
        int R = dp.size() - 1;
        int mid = 0 ;
        int ans = dp.size();
        while(L <= R){
            mid = (L + R) / 2;
            if(dp.get(mid).firstKey() >= num){
                ans = mid;
                R = mid - 1;
            }else{
                L = mid + 1;
            }
        }
        return ans;
    }
}
